package com.cheung.leetcode.backtrack;

import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Set;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.backtrack
 * @Author :  cheungming
 * @CreateTime : 2024-05-27 08:48:55
 * @Description : 非递减子序列
 * @Version : 1.0
 */
public class Code491Test {

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new java.util.ArrayList<>();
        backtrack(nums, 0, new java.util.ArrayList<>(), res);
        return res;
    }

    public void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() > 1 && path.size() <= nums.length) {
            res.add(new java.util.ArrayList<>(path));
        }
        Set<Integer> set = new java.util.HashSet<>();
        for (int i = start; i < nums.length; i++) {
            // 剪枝,如果当前元素小于path最后一个元素或者当前元素已经出现过，则跳过
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || set.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            set.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }

    }


    @Test
    public void test1() {
        int[] nums = {4, 6, 7, 7};
        System.out.println(findSubsequences(nums));
        assert findSubsequences(nums).equals(List.of(List.of(4, 6), List.of(4, 6, 7), List.of(4, 6, 7, 7), List.of(4, 7), List.of(4, 7, 7), List.of(6, 7), List.of(6, 7, 7), List.of(7, 7)));
    }

    @Test
    public void test2() {
        int[] nums = {4, 4, 3, 2, 1};
        System.out.println(findSubsequences(nums));
        assert findSubsequences(nums).equals(List.of(List.of(4, 4)));
    }
}
